1. Field of the Invention
The present invention relates to an associative memory. It particularly relates to an associative memory which can replace an entry most efficiently and makes an easy compare operation test.
2. Description of the Prior Art
There has not been available a technique capable of detecting a HIT entry number in the conventional associative memory. Instead, used is a HIT/MIS(not HIT) detection circuit for associative memory or a circuit for detecting a HIT in more than an entry, that is, a multiple selection of the entries.
In the conventional case where the HIT entry number cannot be detected, merely detected is the information whether an address is hit or not. Thus, test reliability of the associative memory system is low. In other words, even if a test vector is executed to detect a HIT signal in a test manner that, say, a 5th entry is to be hit in a Translation Lookaside Buffer (TLB) with 16 entries, it is most probable that the 5th entry is actually not hit (MIS) while other entry than the 5th entry is hit. This happens due to the fact that the HIT signal cannot specify securely that the entry hit is the 5th entry. However, it is possible to make the test vector that can solve the above problem, resulting in a very complicated test vector. If the hit entry number can be detected, above procedure will be carried out with ease and accuracy.
For example, a CAM (Content Addressable Memory) cell constituting a CAM cell array 1 comprises a flip-flop for storing data and an EXOR (Exclusive OR) circuit, as illustrated to FIG. 1 and FIG. 2. Each entry in the EXOR circuit of the CAM cell is connected to a match line CML.sub.i crossing the array. The match line CML.sub.i operates a search during a pre-charge duration T.sub.p.
Each entry data is compared in parallel with the data inputted from the outside. As a result of the comparison, the match line of the entry remains High ("H") when matched (HIT); the match line of such entry is discharged as Low ("L") by the EXOR circuit in the CAM cell when not HIT (MIS). Then, a word line RWL.sub.i responsive to the HIT entry in the RAM cell array 3 becomes open, and the data is read out.
However, the entry is selected at random when the replacement of the entry is executed in the associative memory. Thus, there is concern that the most recently HIT entry may be replaced anew. In other words, since the most recently hit entry has a high probability to be accessed next, it is inefficient to replace anew and discharge such a most recently hit entry. Further, at testing, it is hard to verify the compare-operation on all entries under such condition.
As described above, prior art associative memory suffers from some significant disandvantages among which is the inefficiency caused by selecting the entry by the random replacement when renewing data in the associative memory. By the same token, it is difficult to verify the compare operation on all entries at testing.